/*
带有检查的内存分配器。可以检查指针是否有效的堆指针，以及是否是 Mem_alloc Mem_calloc 和 Mem_resize 返回的指针。
并且这三个函数从来不会把同一地址返回两次。举个例子，比如返回了相同的地址，如果第一次返回的指针在内存被 free 后，
一直没有被设置为 NULL 那么对这个指针调用 free 是正常的操作，但是释放的是第二次分配的内存，就产生了错误。

这个分配器的缺点，
 分配时查找空闲块时的效率是 O(N) 。
 连续的小空闲块不能合并，会导致有效使用率很低。
 分配的 Descriptor 被添加到 _free_list 并不会被回收，所以有可能产生很多 size 小于等 sizeof(AlignTag) 的无用空闲块，
并且当 size 等于 0 时，会产生相同的 ptr 在空闲链表中。
**/

#include "mem.h"

#include "assert.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

union AlignTag {
	int i;
	long l;
	long *lp; // 这个和 void* 是一样字节数，不知道为什么要添加这个定义
	void *p;
	void (*fp)(void);
	float f;
	double d;
	long double ld;
};

typedef struct Descriptor Descriptor;
struct Descriptor {
	Descriptor *free;
	Descriptor *link;
	void *ptr;
	long size;
	const char *file;
	int line;
};

static Descriptor *_hash_dp[2048];
// 空闲内存块列表，每次必须在头部插入，确保相同的 ptr 时 size 为 0 的空闲快位于排在后面，不被搜索到。
static Descriptor _free_list = {&_free_list, NULL, NULL, 0, NULL, 0};

// 对齐到 AlignTag 字节数
#define ALIGN_SIZE(n) ((n) + sizeof(union AlignTag)-1) / sizeof(union AlignTag) * sizeof(union AlignTag) 
#define HASH_KEY(p) (((size_t)p>>3) & (sizeof(_hash_dp)/sizeof(_hash_dp[0])-1))

const Except_T ex_mem_alloc_failed = {"memory alloc failed"};

static Descriptor*
dalloc(void *ptr, long size, const char *file, int line) {
	const int BATCH_NUM = 1024;
	static Descriptor *arr = NULL;
	static int left = 0;
	if (left <= 0) {
		arr = malloc(BATCH_NUM * sizeof(*arr));
		if (arr == NULL)
			return NULL;
		left = BATCH_NUM;
	}

	Descriptor *dp = &arr[BATCH_NUM - left];
	left--;

	dp->ptr = ptr;
	dp->size = size;
	dp->file = file;
	dp->line = line;
	dp->free = dp->link = NULL;
	return dp;
}

static Descriptor*
dfind(void *ptr) {
	int key = HASH_KEY(ptr);
	for (Descriptor *dp = _hash_dp[key]; dp; dp = dp->link) {
		if (dp->ptr == ptr && dp->free == NULL)
			return dp;
	}
	assert(0);
	return NULL;
}

void* Mem_alloc(long nbytes, const char *file, int line) {
	assert(nbytes > 0);
	nbytes = ALIGN_SIZE(nbytes);

	void *ptr;
	for (Descriptor *dp = _free_list.free; ; dp = dp->free) {
		// 这里隐患时会出现相同的 ptr 指针，一个是 size 为 0 的空闲块，另一个是 size 大小的数据块，
		// 当数据块被回收后，若再次分配刚好 size 大小的数据块，那么被回收后又会产生一个相同 ptr 而 size 为 0 的空闲块。
		// 虽然相同的 ptr 被 hash 到同一个 slot 但是 size 为 0 的空闲块会被置入链表的后部，
		// 这样回收时，不会被搜索到，所以程序能正常运行。
		if (dp->size > nbytes) {
			// 找到满足的条件的空闲块后，取出需要的字节数
			dp->size -= nbytes;
			ptr = (char*)(dp->ptr) + dp->size;
			// 创建新的块，记录本次分配
			Descriptor *sel = dalloc(ptr, nbytes, file, line);
			if (sel == NULL) {
				if (file)
					except_raise(&ex_mem_alloc_failed, file, line);
				else
					RAISE(ex_mem_alloc_failed);
			}
			int key = HASH_KEY(ptr);
			sel->link = _hash_dp[key];
			_hash_dp[key] = sel;
			return ptr;
		}

		// 未找到满足条件的空闲块，则分配空闲块后再次查找
		if (dp == &_free_list) {
			const int FREE_BLOCK_SIZE = ALIGN_SIZE(4096);
			ptr = malloc(FREE_BLOCK_SIZE + nbytes);
			if (ptr == NULL) {
				if (file)
					except_raise(&ex_mem_alloc_failed, file, line);
				else
					RAISE(ex_mem_alloc_failed);	
			}

			Descriptor *desc = dalloc(ptr, FREE_BLOCK_SIZE + nbytes, file, line);
			if (desc == NULL) {
				if (file)
					except_raise(&ex_mem_alloc_failed, file, line);
				else
					RAISE(ex_mem_alloc_failed);	
			}

			desc->free = _free_list.free;
			_free_list.free = desc;
		}
	}
	assert(0);
}

void* Mem_calloc(long count, long nbytes, const char *file, int line) {
	assert(count > 0);
	assert(nbytes > 0);
	void *ptr = Mem_alloc(count * nbytes, file, line);
	memset(ptr, 0, count * nbytes);
	return ptr;
}

void* Mem_resize(void *ptr, long nbytes, const char *file, int line) {
	assert(ptr);
	assert(nbytes > 0);

	Descriptor *dp = NULL;	
	if (((size_t)ptr & (sizeof(union AlignTag) - 1))!=0 || 
		(dp = dfind(ptr)) == NULL ||
		dp->free) {
		if (file)
			except_raise(&ex_mem_alloc_failed, file, line);
		else
			RAISE(ex_mem_alloc_failed);
	}
	
	void *dest = Mem_alloc(nbytes, file, line);
	memcpy(dest, ptr, nbytes > dp->size ? dp->size : nbytes);
	Mem_free(ptr, file, line);
	return dest;
}

void Mem_free(void *ptr, const char *file, int line) {
	if (ptr) {
		Descriptor *dp = NULL;	
		if (((size_t)ptr & (sizeof(union AlignTag) - 1))!=0 || 
			(dp = dfind(ptr)) == NULL ||
			dp->free) {
			if (file)
				except_raise(&ex_mem_alloc_failed, file, line);
			else
				RAISE(ex_mem_alloc_failed);
		}
		dp->free = _free_list.free;
		_free_list.free = dp;	
	}
}

void Mem_debug(int nfree, int use_bytes) {
	int n = 0;
	long total = 0;
	for (Descriptor *dp = _free_list.free; ; dp = dp->free) {
		if (dp == &_free_list)
			break;
		n++;
		total += dp->size;
	}
	printf("total num free:%d use num free:%d\ntotal free bytes:%ld use bytes:%d, use percent:%.3f\n", 
		n, nfree, total, use_bytes, (double)use_bytes/total);

	int nslot = 0, ndp = 0;
	for (int i = 0; i < (int)(sizeof(_hash_dp)/sizeof(_hash_dp[0])); i++) {
		Descriptor *dp = _hash_dp[i];
		if (dp == NULL)
			continue;
		nslot++;
		while (dp) {
			ndp++;
			dp = dp->link;
		}
	}
	printf("num slot:%d, total num dp:%d, total num slot:%d\n", 
		nslot, ndp, (int)(sizeof(_hash_dp)/sizeof(_hash_dp[0])));
}
